package uebung4;

interface Hashfunktion<K> {
	public int hashkey(K key, int hashTablelength);
}

public class Hashing<K, D> {

	Hashfunktion<K> h;

	class Node<K, D> {
		public Node(K key, D data) {
			m_Key = key;
			m_Data = data;
		}

		private K m_Key;
		private D m_Data;
	}

	public Hashing(Hashfunktion<K> h) {
		this.h = h;
		m_Entries = new Node[1023];
		m_iNrOfEntries = 0;
	}

	public D search(K key) {
		int iIndex = h.hashkey(key, m_Entries.length);
		for (int i = 0; m_Entries[iIndex] != null && i < m_Entries.length; ++i) {
			if (m_Entries[iIndex].m_Key == key)
				return m_Entries[iIndex].m_Data;
			iIndex = (iIndex + 1) % m_Entries.length;
		}
		return null;
	}

	public void insert(K key, D data) {
		int iIndex = h.hashkey(key, m_Entries.length);
		for (int i = 0; i < m_Entries.length; ++i) {
			if (m_Entries[iIndex] == null) {
				m_Entries[iIndex] = new Node<K, D>(key, data);
				++m_iNrOfEntries;
				if (m_iNrOfEntries > m_Entries.length * 8 / 10)
					resize();
				return;
			}
			iIndex = (iIndex + 1) % m_Entries.length;
		}
	}

	public void remove(K key) {
		int iIndex = h.hashkey(key, m_Entries.length);

		System.out.println(iIndex);

		for (int i = 0; m_Entries[iIndex] != null && i < m_Entries.length; ++i) {
			if (m_Entries[iIndex].m_Key == key) {
				m_Entries[iIndex] = null;
				System.out.println(iIndex + " geloescht!");
				return;
			}
			iIndex = (iIndex + 1) % m_Entries.length;
		}
	}

	private void resize() {
		final int OLDCAPACITY = m_Entries.length;
		Node<K, D>[] oldEntries = m_Entries;
		final int iNewCap = (m_Entries.length + 1) * 2 - 1;
		m_Entries = new Node[iNewCap];
		m_iNrOfEntries = 0;
		for (int i = 0; i < OLDCAPACITY; ++i) {
			if (oldEntries[i] != null) {
				insert(oldEntries[i].m_Key, oldEntries[i].m_Data);
			}
		}
	}

	private Node<K, D>[] m_Entries;
	private int m_iNrOfEntries;
}
